package sortArrayByParityII;
import java.util.LinkedList;
public class Solution {
    public int[] sortArrayByParityII(int[] nums) {
//        LinkedList<Integer> list = new LinkedList<>();
//        for (int i = 0; i < nums.length; i++) {
//            if(nums[i]%2 == 0){
//                list.addFirst(nums[i]);
//            }else {
//                list.addLast(nums[i]);
//            }
//        }
//        for (int i = 0; i+1< list.size(); i+=2) {
//            nums[i] = list.pollFirst();
//            nums[i+1] = list.pollLast();
//        }
//        return nums;
        // 双指针
//        int oddIndex = 1; // 奇数索引
//        int evenIndex = 0; // 偶数索引
//        int[] ans = new int[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//            if(nums[i]%2==0) {
//                ans[evenIndex] = nums[i];
//                evenIndex+=2;
//            }else {
//                ans[oddIndex] = nums[i];
//                oddIndex+=2;
//            }
//        }
//        return ans;

        // 遍历整个nums，判断nums[i]和i的奇偶性的
//        for (int i = 0; i < nums.length; i+=2) {
//            if(nums[i]%2==0&&i%2!=0){
//                // 找到下一个奇数和位置不平衡的
//                for (int j = i+1; j < nums.length; j+=2) {
//                    if(nums[j]%2!=0){
//                        int t = nums[j];
//                        nums[j] = nums[i];
//                        nums[i] = t;
//                    }
//                }
//            }else if(nums[i]%2!=0&&i%2==0){
//                // 找到下一个偶数和位置不平衡的
//                for (int j = i+1; j < nums.length; j+=2) {
//                    if(nums[j]%2==0){
//                        int t = nums[j];
//                        nums[j] = nums[i];
//                        nums[i] = t;
//                    }
//                }
//            }
//        }
//        return nums;


        // 思路
        // 用所有偶数不平衡的和奇数不平衡的交换即可
        int n = nums.length;
        int j = 0;
        for (int i = 1; i < n; i+=2) {
            if(nums[i]%2==0){
                // 偶数不平衡的 因为i始终是奇数
                // 找到一个奇数不平衡的
                while (nums[j] % 2 == 0) {
                    j += 2;
                }
                swap(nums,i,j);
            }
        }
        return nums;
    }
    private void swap(int []nums,int i,int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
